// https://leetcode.cn/problems/combination-sum-iii/
// Created by ade on 2022/9/9.
//
#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    // k个数 n和
    vector <vector<int>> res = {};

    vector <vector<int>> combinationSum3(int k, int n) {
        for (int i = 1; i <= 9; i++) {
            vector<int> tmp = {i};
            combine(tmp, k - 1, n - i, i);
        }
        return res;
    }

    void combine(vector<int> &tmp, int k, int n, int num) {
        if (k == 0 && 0 == n) {
            res.push_back(tmp);
            return;
        }
        for (int i = num + 1; i <= 9; i++) {
            if (n - i < 0) break;
            tmp.push_back(i);
            combine(tmp, k - 1, n - i, i);
            tmp.pop_back();
        }
    }


};

int main() {
    Solution so;
    auto res = so.combinationSum3(3, 9);
    for (auto items: res) {
        for (auto i:items) {
            cout << i << ",";
        }
        cout << endl;
    }
    return 0;
}